/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-07-07
 * Time: 21:22
 */
//创建一棵二叉搜索树
public class SearchTree {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root ;


    //插入数据 ,构建二叉搜索树
    public boolean insert( int val) {
        //插入时 , 如果root 节点为空 ,创建一个根节点
        if( root == null) {
            root = new TreeNode(val);
        }
        //分别定义 一个 cur 和 prev指针 , cur进行动 , prev记录上一个位置
        TreeNode cur = root;
        TreeNode prev = root;
        //当cur 不为空 时,进行比较插入, 当数据有重复时,不能进行插入 ,返回false
        //当数据小于 cur.val时 ,树的左边进行插入 , 大于往右边插入
        while( cur!=null) {
            if( cur.val < val) {
                prev = cur;
                cur = cur.right;
            } else if( cur.val > val) {
                prev = cur;
                cur = cur.left;
            } else {
                return false;
            }
        }
        //代码走到这 , cur = null , 判断val应该插入prev的左边还是右边
        if( prev.val < val ) {
            prev.right = new TreeNode( val);
        } else {
            prev.left= new TreeNode( val);
        }
        return true;
    }

    //查找数据
    public TreeNode search( int key) {
        if( root == null) return null;
        TreeNode cur = root;
        while( cur!=null) {
            if( cur.val == key) {
                return cur;
            } else if ( cur.val < key) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return null;
    }

    /**
     * 删除节点 :
     * 1 . 找到要删除的节点
     * 2.  进行删除操作
     *     分为以下情况 :
     *      要删除节点的前一节点为 prev
     *      当 要删除的节点cur 的左节点为空 :
     *                                    1. if(cur = root)   :  让 root = cur.right;
     *                                    2. else if ( cur == prev.left)  prev.left = cur.right
     *                                    3. else  prev.right = cur.right
     *                      的右节点为空 :
     *                                   1. if( cur = root) : 让 root = cur.left;
     *                                   2. else if( cur == prev.left) prev.left = cur.left;
     *                                   3. else   prev.right = cur.left
     *                      左右节点都不为空 :  采用替换法 , 在cur的左子树找最大值 , 或者在cur的右子树找最小值 target替换cur,再删除target位置的节点
     *
     * @param
     */
    //1. 先找到要删除的节点
    public boolean remove(  int key) {
        if( root == null) return false;
        TreeNode cur = root;
        TreeNode prev = root;
        while( cur != null) {
            if( cur.val < key) {
                prev= cur;
                cur = cur.right;
            } else if( cur.val == key) {
                delete( prev,cur);
                System.out.println("删除成功!");
                return true;
            } else {
                prev = cur;
                cur = cur.left;
            }
        }
        System.out.println( "删除的节点不存在");
        return true;
    }
    //2. 删除节点
    private void delete( TreeNode prev ,TreeNode cur) {
        // 1. cur .left = null
        if( cur.left == null) {
            if( cur == root) {
                root = cur.right;
            } else if( cur == prev.left) {
                prev.left = cur.right;
            } else {
                prev.right = cur.right;
            }
        } else if( cur. right == null) {   //cur.right 为空
            if( cur == root) {
                root = cur.left;
            } else if( cur == prev.left) {
                prev.left = cur.left;
            } else {
                prev.right = cur.left;
            }
        } else {   //左右都不为空 ,采用替换法 找右子树的最小值target替换 cur ,然后删除 target所在的节点
            TreeNode target = cur.right;
            TreeNode targetparent = cur;
            //找 右子树的最小值
            while( target.left != null) {
                targetparent = target;
                target = target.left;
            }
            //此时 ,target为右子树的最小值 ,进行替换
            cur.val = target.val;
            //删除 target所在的节点
            if( target == targetparent.left) {
                targetparent.left = target.right;
            } else if( target == targetparent.right) {
                targetparent.right = target.right;
            }
        }
    }
    //中序遍历判断是否构建成功 , 构建成功应该是中序遍历结果有序的
    public  void inorder( TreeNode root) {
        if( root == null) {
            return;
        }
        inorder( root.left);
        System.out.print( root.val + " ");
        inorder( root.right);
    }
}
